CS589 ASSIGNMENT 4

Name: Dorian Benhamou Goldfajn
Email: dbenhamougol@umass.edu
Discussed With: Aryan Nair

Question 1

• In theory, increasing the numbers of clusters should retain more of the original data and therefore cost more but be more accurate. However, a lot of clusters are consequently prone to overfitting the data. The idea behind the 'elbow' rule is to find the the point where adding another cluster is not longer worth the extra information in comparison to the cost. The "elbow" is that cutoff point representing the optimal number of clusters to choose.

• K-means doe not guarantee to find optimal solution due to its dependence on initialization. K-means++ aims to give you some guaranteed approximation factor by cleverly choosing initial cluster centers. The cluster centers are based on initial points and K-means++ tries to maximize the distance between the cluster centers. It turns out that this initialization step gives you the guarantee.

Question 2

import numpy as np 
import sklearn
import matplotlib.image as mpimg
import matplotlib.pyplot as plt

import sklearn.cluster

def find_chunk(y,x, img_x):
    return (y//3)*(img_x//3) + x//3

def flat_chunk(chunk):
    res = []
    for row in chunk:
        for pixel in row:
            for c in pixel:
                res.append(c.astype(np.float32))
    return res

k_list = [2, 5, 10, 50, 200, 500, 1000, 2000]
img = mpimg.imread('cityview.png') # colors between 0 and 1

# split image into 3 by 3 chunks
index_chunk_dict = {}
chunks = np.array([img[i:i+3, j:j+3] for i in range(0, img.shape[0], 3) for j in range(0, img.shape[1], 3) ])

# transform each chunk into a vector
matrix = np.array([flat_chunk(chunk) for chunk in chunks])


reconstructed_images = []
reconstructed_img = img.copy()

for k in k_list:
    
    reconstructed_img = img.copy()

    # apply k-means clustering
    centroids, label, inertia = sklearn.cluster.k_means(matrix, k)

    # reconstruct image
    for y in range(0, img.shape[0], 3):
        for x in range(0, img.shape[1], 3):
            chunk_index = find_chunk(y,x,img.shape[1])
            cluster_number = label[chunk_index]
            cluster_vector = centroids[cluster_number]
            reshaped_vector = cluster_vector.reshape(3, 3, 3)
            reconstructed_img[y:y+3, x:x+3] = reshaped_vector
           
    reconstructed_img = reconstructed_img.astype(np.float32)
    print("k = ", k)
    plt.imshow(reconstructed_img)
    plt.show()
    reconstructed_images.append(reconstructed_img.copy())
    

k =  2

k =  5

k =  10

k =  50

k =  200

k =  500

k =  1000

k =  2000

Question 3

recon_errors = {}
k_list = [2, 5, 10, 50, 200, 500, 1000, 2000]
for i, recon_img in enumerate(reconstructed_images):
    e = (img - recon_img)**2
    k = k_list[i]
    recon_errors[k] = e.mean()

print('k , mean squared error\n')
for item in recon_errors.items():
    print(item, '\n') 

k , mean squared error

(2, np.float32(0.028688248)) 

(5, np.float32(0.012967184)) 

(10, np.float32(0.009750629)) 

(50, np.float32(0.0054576797)) 

(200, np.float32(0.0036261887)) 

(500, np.float32(0.002817617)) 

(1000, np.float32(0.0023217162)) 

(2000, np.float32(0.0018872514)) 

Question 4

# need chunk array - 111280
# need label array - 111280 ??
# need array centroids of size k * 27

# original size is 111,280 (chunks) elements of size 27
# new size is 111,280 (chunks) elements matched to one of k clusters of size 27
# before, each chunk had 27 unique numbers associated with it
# now, multiple chunks are matched to a single cluster vector of size 27 out of k clusters

# now, k * 27 + 111280 * 1 (now each chunk has a single cluter index associated with it, instead of 27. Each index is associated with a vector of 27 numbers)



compressed_sizes = {}
print("k : total numbers\n")
for k in k_list:
    compressed_sizes[k] = k*27 + 1 * 111280
    print(k, ':', k * 27 + 1 * 111280, '\n')

k : total numbers

2 : 111334 

5 : 111415 

10 : 111550 

50 : 112630 

200 : 116680 

500 : 124780 

1000 : 138280 

2000 : 165280 

Question 5

# Compression rate = compressed size / original size

original_size = 1284 * 780 * 3
print("k : compression rate\n")
for k in k_list:
    print(k, ':', compressed_sizes[k] / original_size, '\n')

k : compression rate

2 : 0.03705500971856112 

5 : 0.037081968740847245 

10 : 0.037126900444657454 

50 : 0.037486354075139124 

200 : 0.038834305189445376 

500 : 0.041530207418057886 

1000 : 0.04602337779907873 

2000 : 0.05500971856112043 

Question 6

from IPython.display import Image
Image(filename='IMG_0043.jpg', width=800)

Question 7

Image(filename='IMG_0044.jpg', width=800)

Question 8

Image(filename='IMG_0045.jpg', width=800)

Image(filename='IMG_0046.jpg', width=800)

Question 9

Image(filename='IMG_0047.jpg', width=800)

Question 10

original_img = mpimg.imread('portrait.png') # load img
print("original image")
plt.imshow(original_img)
plt.show()
original_img_vector = original_img.flatten() # turn image to vector of 9000 dimensions
k_list = [3, 5, 10, 30, 50, 100, 200, 500, 1000]
# get mean of all images in portraits folder
image_vectors= []
for i in range(1000):
    img = mpimg.imread('portraits/portrait_' + str(i) + '.png')
    img_vector = img.flatten()
    image_vectors.append(img_vector)


# get cov matrix
image_vectors = np.array(image_vectors)
cov_matrix = np.cov(image_vectors, rowvar=False)

# get eigenvectors
eig_vals, eig_vecs = np.linalg.eigh(cov_matrix)

sorted_indices = np.argsort(eig_vals)[::-1]  # Get indices of sorted eigenvalues in descending order
eig_vals = eig_vals[sorted_indices]  # Sort eigenvalues
eig_vecs = eig_vecs[:, sorted_indices]  # Sort eigenvectors according to eigenvalues


for k in k_list:

    # project original image onto k eigenvectors
    y = []
    for j in range(k):
        eigen_vector = eig_vecs[:, j]
        y.append(np.dot(eigen_vector.T, original_img_vector))
    
    # reconstruct original image
    reconstructed_img = [float(0) for i in range(9000)]
    for j in range(len(y)):
        reconstructed_img += (y[j] * eig_vecs[:, j])
    reconstructed_img = np.array(reconstructed_img)
    # scale all numbers to (0-1)
    reconstructed_img = np.clip(reconstructed_img, 0, 1)
    reconstructed_img = reconstructed_img.reshape(60,50,3)
    print("k = ", k)
    plt.imshow(reconstructed_img)
    plt.show()

original image

k =  3

k =  5

k =  10

k =  30

k =  50

k =  100

k =  200

k =  500

k =  1000

Question 11

compressed_sizes = {}
for k in k_list:
    compressed_sizes[k] = k * 1000  + k * 9000

# Compression rate = compressed size / original size

original_size = 1000 * 60 * 50 * 3 # 1000 images 
print("k : compression rate\n")
for k in k_list:
    print(k, ':', compressed_sizes[k] / original_size, '\n')

k : compression rate

3 : 0.0033333333333333335 

5 : 0.005555555555555556 

10 : 0.011111111111111112 

30 : 0.03333333333333333 

50 : 0.05555555555555555 

100 : 0.1111111111111111 

200 : 0.2222222222222222 

500 : 0.5555555555555556 

1000 : 1.1111111111111112